#include <stdlib.h>
#include <stdio.h>
#include <stack>
#include <vector>

using namespace std;

typedef char ElemType;

typedef struct tnode {
    ElemType data;	//数据域
    struct tnode *lchild,*rchild;	//指针域
} BTNode;

BTNode* createTree(char str[]) {
	BTNode* root = NULL;
	BTNode* p = NULL;
	stack<BTNode*> s;
	int k = 1;
	for (int i=0; str[i] != '\0'; i++) {
		char c = str[i];
		switch(c) {
			case '(': 
				k = 1;
				s.push(p);
				break;
			case ')':
				s.pop();
				break;
			case ',':
				k = 2;
				break;
			default:
				p = (BTNode*)malloc(sizeof(BTNode));
				p->data = c;
				p->lchild = p->rchild = NULL;
				if (root == NULL) {
					root = p;
				} else {
					BTNode* parent = s.top();
					if (k == 1) {
						parent->lchild = p;
					} else {
						parent->rchild = p;
					}
				}
		} // end switch
	} // end for
	return root;
}

int BTHeight(BTNode *bt) {
    int lchilddep, rchilddep;
    if (bt == NULL) return(0);	//空树的高度为0
    else {
        lchilddep = BTHeight(bt->lchild);	//求左子树的高度为lchilddep
        rchilddep = BTHeight(bt->rchild);	//求右子树的高度为rchilddep
        return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1);
    }
}

void PrintBlank(int n) {
    for (int i = 0; i < n; i++) {
        printf(" ");	//打印n个空格
    }
}

// 将二叉树bt的结点按层次存入数组levelNodes中，
// idx表示当前结点在数组中的位置，
void LinkedTree2Vector(BTNode *bt, std::vector<BTNode *> &levelNodes, const int idx) {
    if (bt == NULL) return;	//空树返回
    levelNodes[idx] = bt;	//将当前结点存入数组
    LinkedTree2Vector(bt->lchild, levelNodes, 2 * idx + 1);	//递归处理左子树
    LinkedTree2Vector(bt->rchild, levelNodes, 2 * idx + 2);	//递归处理右子树
}

void DrawTree(BTNode *bt) {
    if (bt == NULL) return;	//空树返回
    int height = BTHeight(bt);	//计算树的高度
    int maxNum = (1 << height) - 1;	//计算树的最大结点数

    std::vector<BTNode *> levelNodes(maxNum, NULL);
    LinkedTree2Vector(bt, levelNodes, 0);	//获取当前层的节点

    for (int level = 1; level <= height; level++) {
        int leftBlank = 1 << (height - level);	//计算当前层的左侧空格数
        int midBlank = (1 << (height - level + 1)) - 1;	//计算当前层的中间空格数
        PrintBlank(leftBlank);    //打印左侧空格
        int start = (1 << (level - 1)) - 1;	//当前层的起始位置
        int end = (1 << level) - 2;	//当前层的结束位置
        for (int i = start; i <= end; i++) {
            if (levelNodes[i] != NULL) {
                printf("%c", levelNodes[i]->data);	//打印当前节点数据
            } else {
                printf(" ");	//打印空格
            }
            PrintBlank(midBlank);	//打印中间空格
        }
        printf("\n");
    }
}

int main() {
	char *s = "A(B(D,E(G,H)),C(,F(I)))";
	BTNode* tree = createTree(s);
	DrawTree(tree);
	return 0;
}